Random Oracles are Practical: A Paradigm for Designing Efficient Protocols.

We argue that the random oracle model ---where all parties have access to a public random oracle--- provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol $P$ is produced by first devising and proving correct a protocol $P^R$ for the random oracle model, and then replacing oracle accesses by the computation of an ``appropriately chosen'' function $h$. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.